A pattern matching query takes a data string and a query pattern string, and determines whether the pattern of the query pattern string occurs as a substring of the data string. For example, the data string may be a genome sequence and the query pattern string may be a particular sequence of genetic code. A pattern matching query may be performed on data strings that are stored on one or more cloud servers. Often, large and important data strings are stored on such cloud servers because these servers offer virtually limitless storage capacity and robust data backup protection again data loss. Nevertheless, cloud servers may be vulnerable to unauthorized access and the data strings stored on these cloud servers may be compromised or stolen. Thus, a user who owns the data strings may desire to store the data strings as encrypted data on a cloud server, so that the data is protected even when a cloud server is compromised by a malicious attack or unauthorized access.
However, in order to perform pattern matching query on an encrypted data string, the user is generally faced with two equally undesirable choices. One of such choices is to reveal the encryption key used to encrypt the data string to a cloud server, so that the encrypted data string may be decrypted at the server for pattern matching comparison. However, the revelation of the encryption key to the cloud server may provide a malicious perpetrator who has access to the cloud server with the ability to decrypt and steal the data. The other undesirable choice is to download the entire encrypted data string to a client device, then decrypt the encrypted data string and perform the pattern matching query on the decrypted data string at the client device. However, such an approach may be time consuming and inefficient for the purpose of generating pattern matching query results. Further, such an approach is unavailable for data strings that are larger than the storage capacity of the client device.